package st;


public class BST<Key extends Comparable<Key>, Val> implements ST<Key, Val> {
    private Node root;

    @Override
    public void put(Key key, Val val) {
        root = putFromNode(root, key, val);
    }

    public Node putFromNode(Node node, Key key, Val val) {
        if (node == null) {
            return new Node(key, val, 1);
        }

        int cmp = key.compareTo(node.key);
        if (cmp == 0) {
            node.val = val;
            return node;
        } else if (cmp < 0) {
            node.left = putFromNode(node.left, key, val);
        } else {
            node.right = putFromNode(node.right, key, val);
        }

        node.N = sizeOfNode(node.left) + sizeOfNode(node.right) + 1;
        return node;
    }

    @Override
    public Val get(Key key) {
        return getFromNode(root, key);
    }

    public Val getFromNode(Node node, Key key) {
        if (node == null) {
            return null;
        }

        int cmp = key.compareTo(node.key);
        if (cmp == 0) {
            return node.val;
        } else if (cmp < 0) {
            return getFromNode(node.left, key);
        } else {
            return getFromNode(node.right, key);
        }
    }

    @Override
    public void delete(Key key) {

    }

    @Override
    public boolean contains(Key key) {
        return containsFromNode(root, key);
    }

    public boolean containsFromNode(Node node, Key key) {
        Val val = getFromNode(node, key);
        return val != null;
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    @Override
    public int size() {
        return sizeOfNode(root);
    }

    public int sizeOfNode(Node node) {
        return node == null ? 0 : node.N;
    }

    @Override
    public Iterable<Key> keys() {
        return null;
    }

    public Node min() {
        return minFromNode(root);
    }

    public Node minFromNode(Node node) {
        if (node == null) {
            return null;
        }
        if (node.left == null) {
            return node;
        } else {
            return minFromNode(node.left);
        }
    }

    public Node max() {
        return maxFromNode(root);
    }

    public Node maxFromNode(Node node) {
        if (node == null) {
            return null;
        }

        if (node.right == null) {
            return node;
        } else {
            return maxFromNode(node.right);
        }
    }

    private class Node {
        private Key key;
        private Val val;
        private Node left, right;
        private int N;

        Node(Key key, Val val, int n) {
            this.key = key;
            this.val = val;
            this.N = n;
        }


    }

    public static void main(String[] args) {
        BST<String, Object> bst = new BST<>();
        bst.put("name", "zhangsan");
        bst.put("age", 23);
        bst.put("addr", "shandong");

        System.out.println(bst.max().key);
    }
}
